package leetcode.ge100;

import leetcode.lt100.TreeNode;


class Solution_109 {


    public static void main(String[] args) {
        ListNode listNode = new ListNode(-10);
        listNode.append(-3).append(0).append(5).append(9);
        new Solution_109().sortedListToBST(listNode);
    }

    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(head, Integer.MAX_VALUE);
    }

    private TreeNode sortedListToBST(ListNode head, int length) {
        if (head == null || length == 0) {
            return null;
        }
        ListNode mid = head;
        ListNode end = head;
        int step = 0;
        while (end != null && step < length) {
            end = end.next;
            step++;
            if (step % 2 == 0)
                mid = mid.next;
        }
        TreeNode treeNode = new TreeNode(mid.val);
        treeNode.left = sortedListToBST(head, step / 2);
        treeNode.right = sortedListToBST(mid.next, length - 1 - step / 2);
        return treeNode;
    }


}